package com.hardy.leetcode;

/**
 * 字符串s1和字符串s2是否可以转换成s3
 * User: Ruijie Date: 2016/8/31
 */
public class InterleavingString {

    public static boolean isInterleave(String s1, String s2, String s3) {

        int len1 = s1.length();
        int len2 = s2.length();
        int len3 = s3.length();
        if (len1 + len2 != len3) {
            return false;
        }
        //dp[i][j]表示是否可以从ch1[0...i]和ch2[0....j]中翻转成ch3[0...i+j-1];
        boolean[][] dp = new boolean[len1+1][len2+1];
        dp[0][0] = true;
        for (int i = 1; i < len1+1; i++) {
            dp[i][0] = s3.startsWith(s1.substring(0, i));
        }
        for (int j = 1; j < len2+1; j++) {
            dp[0][j] = s3.startsWith(s2.substring(0, j));
        }
        for (int i = 1; i < len1+1; i++) {
            for (int j = 1; j < len2+1; j++) {
                if ((dp[i - 1][j] && s1.charAt(i - 1) == s3.charAt(i + j - 1))
                    || (dp[i][j - 1] && s2.charAt(j - 1) == s3.charAt(i + j - 1))) {
                    dp[i][j] = true;
                }
            }
        }
        /*
        *  思路：dp题。
        *  状态定义：dp[i][j]表示s1[0 ~ i-1]和s2[0 ~ j-1]可以生成s3[0 ~ i+j-1]
        *  递推公式：dp[i][j]为true 当且仅当 s1.charAt(i - 1) == s3.charAt(i + j - 1) && dp[i - 1][j]  或 s2.charAt(j - 1) == s3.charAt(i + j - 1) && dp[i][j - 1]
        *  初始状态：dp[i][0]为true 当且仅当 s1[0 ~ i] 是 以s3开头的子串, dp[0][j]为true 当且仅当 s2[0 ~ j] 是以 s3开头的子串
       */
        return dp[len1][len2];
    }

    public static void main(String[] args) {
        String s1="";
        String s2="";
        String s3="";
        System.out.println(isInterleave(s1,s2,s3));
    }
}
